package com.xy6.algo.dynamic;


/**
 * 最长连续公共子序列
 * <pre>
 * 给定两个字符串，计算其连续相同的子序列的最大长度
 * 
 * 状态转移方程：
 * if(s1[i] == s2[j]){
  *   len[i][j] = len[i-1][j-1] + 1;
 * } else {
 * 	  len[i][j] = 0;
 * }
 * 
 * </pre>
 * 
 * @author zhang
 * @since 2017-11-10
 */
public class StrictLCS {

	/**
	 * 计算两个字符串的最长连续公共子序列
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static int calc(String s1, String s2){
		int m = s1.length();
		int n = s2.length();
		int[][] len = new int[m][n];
		
		// 保存最大长度
		int max = 0;
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				if(s1.charAt(i) == s2.charAt(j)){
					len[i][j] = len(len, i - 1, j - 1) + 1;
				} else {
					len[i][j] = 0;
				}
				if(len[i][j] > max){
					max = len[i][j];
				}
			}
		}
		
		return max;
	}

	/**
	 * 获取二维数组中某一索引元素
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	private static int len(int[][] len, int i, int j){
		if(i < 0 || j < 0 || i >= len.length || j >= len[0].length ){
			return 0;
		}
		return len[i][j];
	}
	
}
